package solution;

import solution.bean.ListNode;

/*
* 25
* */
public class ReverseKGroup {
    /*
    * 如果题干允许，直接修改值
    * */

    /*
    * 使用迭代法+基本翻转
    * */
//    public ListNode resolution1(ListNode head, int k) {
//        ListNode point = new ListNode(0);
//        point.next = head;
//        ListNode pre = point;
//
//        while (head != null){
//            ListNode tail = pre;
//            for (int i = 0 ; i < k ; i++){
//                tail = tail.next;
//                if (tail == null){
//                    return point.next;
//                }
//            }
//
//            ListNode nex = tail.next;
//            ListNode[] reverse = myReverse(head, tail);
//            head = reverse[0];
//            tail = reverse[1];
//
//            pre.next = head;
//            tail.next = nex;
//            pre = tail;
//            head = tail.next;
//        }
//
//        return point.next;
//    }
//
//    public ListNode[] myReverse(ListNode head, ListNode tail){
//        ListNode prev = tail.next;
//        ListNode p = head;
//        while (prev != tail){
//            ListNode nex = p.next;
//            p.next = prev;
//            prev = p;
//            p = nex;
//        }
//
//        return new ListNode[]{tail,head};
//    }

    /*
    * 优化的解题
    * */
    public ListNode resolution1(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;

        while (pre.next != null){
            ListNode temp = pre;
            for (int i = 0 ; i < k ; i++){
                temp = temp.next;
                if (temp == null){
                    return dummy.next;
                }
            }
            ListNode end = reverse(pre, temp);
            pre = end;
        }

        return dummy.next;
    }


    ListNode reverse(ListNode node1, ListNode node2){
        ListNode start = node1.next;
        ListNode end = node2.next;


        ListNode pre = null;
        ListNode curr = start;
        while (curr != end){
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }

        node1.next = pre;
        start.next = end;

        return start;
    }

    /*
    * 使用递归
    * */
    public ListNode resolution2(ListNode head, int k) {
        if (head == null || head.next == null){
            return head;
        }

        ListNode tail = head;
        for (int i = 0 ; i < k ; i++){
            if (tail == null){
                return head;
            }
            tail = tail.next;
        }

        ListNode newHead = reverseList(head, tail);
        head.next = resolution2(tail, k);
        return newHead;
    }

    public ListNode reverseList(ListNode head, ListNode tail){
        ListNode pre = null;
        ListNode next = null;
        while (head != tail){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}
